import java.util.Arrays;

public class Rob2 {
    // 打家劫舍2
    // https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int rob (int[] nums) {
        // write code here
        // 因为是环形的，所以第一家和最后一家是相连的
        // 所以就需要分三种情况讨论
        // 1. 第一家偷，最后一家不偷
        // 2. 第一家不偷，最后一家偷
        // 3. 第一家和最后一家都不偷
        int len = nums.length;
        return Math.max(Math.max(robFun(Arrays.copyOfRange(nums, 0, len-1)), robFun(Arrays.copyOfRange(nums, 1, len))), robFun(Arrays.copyOfRange(nums, 1, len-1)));
    }

    private int robFun(int[] nums) {
        // write code here
        int len = nums.length;
        // 状态表示
        // f[i]表示第i个房子偷时候的最大金额
        int[] f = new int[len + 1];
        // g[i]表示第i个房子不偷时候的最大金额
        int[] g = new int[len + 1];
        // 状态转移方程
        // f[i] = max(max(f[i-2], g[i-2]), g[i-1]) + nums[i]
        // g[i] = max(max(f[i-1], g[i-1]), f[i-2]);
        f[1] = nums[0];
        for (int i = 2; i <= len; i++) {
            f[i] = Math.max(Math.max(f[i - 2], g[i - 2]), g[i - 1]) + nums[i - 1];
            g[i] = Math.max(Math.max(f[i - 1], g[i - 1]), f[i - 2]);
        }
        return Math.max(f[len], g[len]);
    }
}
